package unionFind;

import java.util.LinkedList;

/***
 * 200. 岛屿数量
 */
public class P200 {
    public int numIslands(char[][] grid) {
        // 转换
        int[][] newGrid = new int[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                newGrid[i][j] = Integer.parseInt(grid[i][j] + "");
            }
        }
        //
        char maxCount = 1;
        //1. 使用BFS
        boolean[][] visited = new boolean[newGrid.length][newGrid[0].length];
        LinkedList<Node> queue = new LinkedList<>();
        for (int i = 0; i < newGrid.length; i++) {
            for (int j = 0; j < newGrid[i].length; j++) {
                if (!visited[i][j]) {
                    if (newGrid[i][j] == 1) { //陆地
                        queue.add(new Node(i, j, ++maxCount));
                        newGrid[i][j]=maxCount;
                    } else { // 水
                        queue.add(new Node(i, j, 0));
                    }
                    // 广度遍历
                    int[][] directions = new int[][]{
                            {0, -1}, {-1, 0}, {0, 1}, {1, 0}
                    };
                    while (!queue.isEmpty()) {
                        Node currNode = queue.poll();
                        for (int[] direct : directions) {
                            int x = currNode.x + direct[0];
                            int y = currNode.y + direct[1];
                            int flag = currNode.flag == 0 ? 0 : 1;
                            if (0 <= x && x < newGrid.length && 0 <= y && y < newGrid[0].length && !visited[x][y] && newGrid[x][y] == flag) {
                                newGrid[x][y] = currNode.flag;
                                visited[x][y] = true;
                                queue.add(new Node(x, y, currNode.flag));
                            }
                        }
                    }
                }
            }
            showGrid(newGrid);
        }
        return maxCount - 1;
    }

    private void showGrid(int[][] grid) {
        System.out.println();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                System.out.print(String.format("%d\t,", grid[i][j]));
            }
            System.out.println();
        }
        System.out.println();
    }


    class Node {
        public int x, y;
        public int flag;

        public Node(int x, int y, int flag) {
            this.x = x;
            this.y = y;
            this.flag = flag;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "x=" + x +
                    ", y=" + y +
                    ", flag=" + flag +
                    '}';
        }
    }

    public static void main(String[] args) {
        char[][] grid = new char[][]{
                {'0', '1', '0', '0', '1', '1', '1', '0', '0', '0', '0', '0', '1', '0', '0', '0', '0', '1', '0', '1'}, {'1', '0', '1', '0', '0', '1', '1', '0', '0', '1', '0', '1', '0', '1', '0', '1', '1', '0', '0', '0'}, {'0', '1', '0', '0', '0', '1', '1', '1', '1', '0', '0', '0', '0', '0', '1', '1', '1', '1', '0', '1'}, {'1', '1', '0', '0', '0', '1', '1', '0', '0', '0', '1', '1', '1', '0', '0', '1', '0', '1', '1', '0'}, {'0', '1', '0', '1', '1', '0', '1', '0', '0', '0', '1', '0', '0', '1', '0', '0', '0', '0', '0', '1'}, {'1', '0', '0', '1', '0', '1', '0', '0', '0', '1', '1', '0', '1', '0', '0', '1', '0', '0', '0', '0'}, {'1', '0', '0', '0', '1', '1', '0', '0', '0', '0', '0', '1', '0', '0', '1', '0', '0', '0', '0', '1'}, {'1', '0', '0', '0', '1', '0', '1', '1', '1', '0', '1', '0', '1', '1', '1', '1', '0', '0', '0', '1'}, {'1', '0', '0', '1', '0', '0', '0', '1', '0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '0', '1'}, {'0', '0', '0', '1', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1', '0', '0', '0', '0', '1', '0'}, {'1', '0', '1', '0', '1', '0', '0', '1', '1', '1', '0', '1', '1', '0', '0', '1', '1', '0', '0', '0'}, {'0', '1', '0', '0', '1', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '0', '0', '0', '1', '0'}, {'1', '0', '0', '0', '1', '1', '1', '0', '1', '0', '0', '0', '1', '0', '1', '0', '1', '0', '0', '1'}, {'0', '0', '0', '0', '1', '0', '1', '1', '0', '1', '0', '1', '0', '1', '1', '1', '1', '0', '0', '0'}, {'0', '1', '1', '0', '0', '0', '0', '1', '0', '0', '1', '1', '1', '0', '0', '1', '1', '0', '1', '0'}, {'1', '0', '1', '1', '1', '1', '1', '1', '0', '1', '1', '0', '1', '0', '0', '1', '0', '0', '0', '1'}, {'1', '0', '0', '0', '1', '0', '1', '0', '0', '1', '0', '1', '0', '0', '1', '0', '0', '1', '1', '1'}, {'0', '0', '1', '0', '0', '0', '0', '1', '0', '0', '1', '1', '0', '1', '1', '1', '0', '0', '0', '0'}, {'0', '0', '1', '0', '0', '0', '0', '0', '0', '1', '1', '0', '1', '0', '1', '0', '0', '0', '1', '1'}, {'1', '0', '0', '0', '1', '0', '1', '1', '1', '0', '0', '1', '0', '1', '0', '1', '1', '0', '0', '0'}
        };
        int count = new P200().numIslands(grid);
        System.out.println(count);
    }
}
